Server-assisted secure function evaluation (SFE) allows two parties to evaluate any function on their respective inputs x and y with the assistance of a server, while maintaining the privacy of both x and y. Efficient SFE algorithms enable a variety of electronic transactions, previously impossible due to mutual mistrust of participants. For example, SFE algorithms have been employed in auctions, contract signing and distributed database mining applications. The problem of secure computation has been solved for both semi-honest and malicious players. Generally, having access to a semi-honest server resolves the problem of malicious circuit generation. As computation and communication resources have increased, SFE has become practical for common use. A malicious SFE model provides a guarantee of complete privacy of the players' inputs. Existing server-assisted SFE algorithms typically employ Garbled Circuits (GCs). For a detailed discussion of GCs, see, for example, Y. Lindell and B. Pinkas, “A Proof of Yao's Protocol for Secure Two-Party Computation,” Journal of Cryptology, 22(2):161-188 (2009).
While such existing server-assisted SFE algorithms have significantly improved the privacy of two party transactions, a number of limitations remain, which, if overcome, could further improve the efficiency, utility and/or security of generic two-party SFE algorithms. For example, in the case of multiple SFE executions between the same parties, there is a need for verifying input consistency between executions. Consider profile matching and match ratio computation. These are the underlying functionalities, for example, in online dating, resume/job matching, profiling for advertisement and other services. In many of these applications, it is important that users cannot manipulate their inputs to extract maximum benefit, but, rather, that the user inputs are consistent among executions. For example, a corporation is running a promotion campaign targeting a certain demographic, and other users should not be able to improperly adjust their profiles to take advantage of the promotion.
A need therefore exists for techniques for ensuring input consistency that allow a party to prove he or she is using the same input that was used in a prior execution.